package L610;

/**
 * @program: javase
 * @description: 股票最大利润1
 * @author: luolidong
 * @create: 2021-06-11 21:49
 * @version: 1.0
 */
public class Demo4 {
    public static void main(String[] args) {
        int[] arr = new int[]{7, 1, 5, 3, 6, 4};
        int i = new Demo4().maxProfit(arr);
        int i2 = new Demo4().maxProfit2(arr);
        System.out.println("i = " + i);
        System.out.println("i2 = " + i2);
    }

    //    public int maxProfit(int[] prices) {
//        int minBuy=Integer.MAX_VALUE;
//        int maxProfit=0;
//        for(int i=0;i<prices.length-1;i++){
//            minBuy=Math.min(minBuy, prices[i]);
//            maxProfit=Math.max(prices[i+1]-minBuy,maxProfit);
//        }
//        return maxProfit;
//    }
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        if (prices.length <= 1) {
            return 0;
        }
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i][1] = Math.max(-prices[i], dp[i - 1][1]);
//            持股已经-prices[i],不持股就直接加
            dp[i][0] = Math.max(prices[i] + dp[i - 1][1], dp[i - 1][0]);
        }
        return dp[prices.length-1][0];
    }
//    可多次买卖
    public int maxProfit2(int[] prices) {
        int[][] dp = new int[prices.length][2];
        if (prices.length <= 1) {
            return 0;
        }
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
//            持股，可能当前不是第一次买了
            dp[i][1] = Math.max(-prices[i]+dp[i-1][0], dp[i - 1][1]);
            dp[i][0] = Math.max(prices[i] + dp[i - 1][1], dp[i - 1][0]);
        }
        return dp[prices.length-1][0];
    }
}
